#include "HiranipraShared.h"

#ifndef _SHARED_COLLECTIONS_LFFREELIST_H_
#define _SHARED_COLLECTIONS_LFFREELIST_H_

namespace Hiranipra {

	// http://www.boyet.com/Articles/LockfreeFreeList.html

	template<class T>
	class LinkNode
	{
	public:
		volatile LinkNode*	Next;
		T					Value;
	};

	template<class T>
	class LFFreeList
	{
	public:
		LFFreeList( uint32 capacity )
		{
			_head = new LinkNode<T>();
			volatile LinkNode<T>* node = _head;
			for( uint32 n = 0; n < capacity; n++ )
			{
				node->Next = new LinkNode<T>();
				node = node->Next;
				node->Value = NULL;
			}
		}

		~LFFreeList()
		{
			LinkNode<T>* node;
			while( ( node = this->AllocateNode( true ) ) != NULL )
				DELETE_PTR( node );
			DELETE_PTR( _head );
		}

		LinkNode<T>* AllocateNode( bool dontAllocate = false )
		{
			volatile LinkNode<T>* node;
			do
			{
				node = _head->Next;
				if( node == NULL )
					return new LinkNode<T>();
			} while( !CAS( &_head->Next, node, node->Next ) );
			node->Next = NULL;
			return ( LinkNode<T>* )node;
		}

		void ReleaseNode( LinkNode<T>* node )
		{
			node->Value = NULL;
			do
			{
				node->Next = _head->Next;
			} while( !CAS( &_head->Next, node->Next, node ) );
		}

	private:
		volatile LinkNode<T>*	_head;
	};

}

#endif // _SHARED_COLLECTIONS_LFFREELIST_H_
